//输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
//
// B是A的子结构， 即 A中有出现和B相同的结构和节点值。
//
// 例如: 给定的树 A:
//
// 3 / \ 4 5 / \ 1 2 给定的树 B：
//
// 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
//
// 示例 1：
//
// 输入：A = [1,2,3], B = [3,1]
//输出：false
//
//
// 示例 2：
//
// 输入：A = [3,4,5,1,2], B = [4,1]
//输出：true
//
// 限制：
//
// 0 <= 节点个数 <= 10000
//
// Related Topics 树 深度优先搜索 二叉树 👍 751 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    if (!A || !B) return false
    const dfs = (A, B) => {
        //? 当B的节点为空时，返回true，因为无论对比的A节点是否为空都满足子结构条件。
        if (!B) return true
        //? 在B的节点不为空时，如果A节点为空则不符合条件为false，不为空则进一步遍历
        //? 满足的条件就是 根节点的值相等 && 遍历左子树的值相等 && 遍历右子树的值相等
        return A ? A.val === B.val && dfs(A.left, B.left) && dfs(A.right, B.right) : false
    }
    //? 递归判断 这一步就在遍历A嘛 每次遍历都在看满不满足条件
    return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};
//leetcode submit region end(Prohibit modification and deletion)
//? 这个代码更易理解一些
function isSubStructure2(A: TreeNode | null, B: TreeNode | null): boolean {
    let result = false
    if (A && B) {
        //? 值相同 开始比较子树
        if (A.val === B.val) result = treeAHasTreeB(A, B)
        //? 没比较成功 继续遍历 因为可能存在相同的值；比较成功 则return了
        if (!result) result = isSubStructure2(A.left, B)
        if (!result) result = isSubStructure2(A.right, B)
    }
    return result
}
const treeAHasTreeB = (A, B) => {
    //? B遍历完了，说明R包含和树B一样的结构
    if (!B) return true
    //? R遍历完了，但是B还没有遍历完，那么B肯定不是R的子结构
    if (!A) return false
    if (A.val !== B.val) return false
    //? 继续遍历AB的左右
    return treeAHasTreeB(A.left, B.left) && treeAHasTreeB(A.right, B.right)
}
